package gold.digger;

import java.util.regex.Pattern;
import java.util.*;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC591 {
    public long startExecuteTime = System.currentTimeMillis();


    /*
     * @param 此题目参考了别人代码
     * 这是因为问题情况较为复杂
     * 此题目垃圾，鉴定完毕
     * @return:
     */

    class Solution {
        private final Pattern PATTERN = Pattern.compile("^[\\da-zA-Z<>/!\\[\\] ]*$");

        private final Pattern START_TAG_PATTERN = Pattern.compile("<[A-Z]+>");

        private final Pattern END_TAG_PATTERN = Pattern.compile("</[A-Z]+>");

        public boolean isValid(String code) {
            if (!PATTERN.matcher(code).matches()) {
                return false;
            }
            Stack<String> stack = new Stack<>();
            char[] codeArray = code.toCharArray();
            for (int i = 0; i < codeArray.length; i++) {
                if (i <= codeArray.length - 9
                        && codeArray[i] == '<'
                        && codeArray[i + 1] == '!'
                        && codeArray[i + 2] == '['
                        && codeArray[i + 3] == 'C'
                        && codeArray[i + 4] == 'D'
                        && codeArray[i + 5] == 'A'
                        && codeArray[i + 6] == 'T'
                        && codeArray[i + 7] == 'A'
                        && codeArray[i + 8] == '[') {
                    // CDATA标签内的所有字符都认为是文本, 不入栈
                    int flag = 0;
                    for (int k = i + 8; k <= codeArray.length - 1; k++) {
                        if (k <= codeArray.length - 3
                                && codeArray[k] == ']'
                                && codeArray[k + 1] == ']'
                                && codeArray[k + 2] == '>') {

                            i = k + 2;
                            flag = 1;
                            break;
                        }
                    }
                    if (flag == 0 || stack.isEmpty()) {
                        return false;
                    }
                } else if (i <= codeArray.length - 2
                        && codeArray[i] == '<'
                        && codeArray[i + 1] >= 65
                        && codeArray[i + 1] <= 90) {

                    // 识别起始标签
                    StringBuilder stringBuilder = new StringBuilder();
                    stringBuilder.append('<');
                    stringBuilder.append(codeArray[i + 1]);
                    boolean findStartTag = false;
                    int k;
                    for (k = i + 2; k <= codeArray.length - 1; k++) {
                        stringBuilder.append(codeArray[k]);
                        if (codeArray[k] == '>') {
                            if (START_TAG_PATTERN.matcher(stringBuilder.toString()).matches()) {
                                if (stringBuilder.toString().length() > 11) {
                                    return false;
                                }
                                findStartTag = true;
                            }
                            break;
                        }
                    }
                    i = k;
                    if (findStartTag) {
                        // 起始标签需要入栈
                        stack.add(stringBuilder.toString());
                    } else {
                        // 如果没找到起始标签, 那么这段代码是纯文本, 纯文本必须包在标签内
                        if (stack.isEmpty()) {
                            return false;
                        }
                    }
                } else if (i <= codeArray.length - 3
                        && codeArray[i] == '<'
                        && codeArray[i + 1] == '/'
                        && codeArray[i + 2] >= 65
                        && codeArray[i + 2] <= 90) {
                    // 识别结尾标签
                    StringBuilder stringBuilder = new StringBuilder();
                    stringBuilder.append('<');
                    stringBuilder.append('/');
                    stringBuilder.append(codeArray[i + 2]);
                    boolean findEndTag = false;
                    int k;
                    for (k = i + 3; k <= codeArray.length - 1; k++) {
                        stringBuilder.append(codeArray[k]);
                        if (codeArray[k] == '>') {
                            if (END_TAG_PATTERN.matcher(stringBuilder.toString()).matches()) {
                                if (stringBuilder.toString().length() > 12) {
                                    return false;
                                }
                                findEndTag = true;
                            }
                            break;
                        }
                    }
                    i = k;
                    if (findEndTag) {
                        boolean findPair = false;
                        // 找到结束标签, 那么成对出现的开始标签出栈
                        while (!stack.isEmpty()) {
                            String top = stack.pop();
                            if (START_TAG_PATTERN.matcher(top).matches()
                                    && !stringBuilder.toString().replace("/", "").equals(top)) {
                                return false;
                            } else if (stringBuilder.toString().replace("/", "").equals(top)) {
                                findPair = true;
                                break;
                            }
                        }
                        if (!findPair || (stack.isEmpty() && i + 1 <= codeArray.length - 1)) {
                            // 未找到成对出现的标签
                            // 或者找到了, 但是后续还有代码, 此时可以断定缺少根标签
                            return false;
                        }
                    } else {
                        // 如果没找到结束标签, 那么这段代码是纯文本, 纯文本必须包在标签内
                        if (stack.isEmpty()) {
                            return false;
                        }
                    }
                } else {
                    if (codeArray[i] == '<') {
                        return false;
                    }
                    stack.add(String.valueOf(codeArray[i]));
                }
            }
            return stack.isEmpty();
        }
    }

    class Solution_Fail_for_Complex {
        public boolean isValid(String code) {
            if (null == code || code.length() <= 3) return false;
            return isValidRecur(code, 0, code.length() - 1, false);
        }

        public boolean isValidRecur(String code, int start, int end, boolean isOuterHasDiv) {
            if (start >= end) return isOuterHasDiv;
            while (start < end) {
                if (code.charAt(start) == '<' && code.charAt(start + 1) != '!') {
                    // 处理当前标签头尾部分
                    if (code.charAt(end) != '>') return false;

                    int tagEndPos = start + 1;
                    Stack<Character> st = new Stack<>();
                    while (tagEndPos <= end && code.charAt(tagEndPos) != '>') {
                        if (!Character.isUpperCase(code.charAt(tagEndPos))) return false;
                        st.push(code.charAt(tagEndPos++));
                    }

                    int sideTagEndPos = end - 1;
                    while (!st.empty() && sideTagEndPos > start) {
                        if (st.pop().charValue() != code.charAt(sideTagEndPos--)) return false;
                    }

                    if (!st.empty()) return false;
                    if (code.charAt(sideTagEndPos) != '/' || code.charAt(sideTagEndPos - 1) != '<') return false;

                    return isValidRecur(code, tagEndPos + 1, sideTagEndPos - 2, true);
                } else if (code.charAt(start) == '<' && code.charAt(start + 1) == '!') {
                    // 当前部分是CDATA
                    if (end - start < 11) return false;
                    if (!code.substring(start, start + 9).equals("<![CDATA[")) return false;
                    int cdataEnd = code.indexOf("]]>", start);
                    if (cdataEnd < 0) return false;
                    return isValidRecur(code, cdataEnd + 3, end, isOuterHasDiv);
                } else {
                    // 当前部分是正文部分
                    ++start;
                }
            }

            return isOuterHasDiv;
        }
    }

    public void run() {
        Solution solution = new Solution();
        System.out.println(solution.isValid("<A><A>456</A>  <A> 123  !!  <![CDATA[]]>  123 </A>   <A>123</A></A>"));
    }

    public static void main(String[] args) throws Exception {
        LC591 an = new LC591();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
